Search results for "Būla funkcijas"
showing 8 items of 8 documents
Atbalsta rīks čaulu programmu izpētei
2017
Čaulu programma ir lineāri algebrisks skaitļošanas modelis. Šis modelis tiek izmantots kvantu skaitļošanas algoritmu izstrādāšanā. Lai atvieglotu čaulu programmu pētīšanu, par darba mērķi tika izvirzīta programmatūras izstrādāšana, kas atbalsta darbu ar čaulu programmām grafiskajā vidē. Darba galvenie uzdevumi ir izstrādājamās programmatūras aprakstīšana, un sekojošu funkciju nodrošināšana: čaulu programmas ievadīšana un rediģēšana, liecības izmēra, sarežģītības un pilnās sarežģītības noteikšana, funkcijas f_P vērtības noteikšana. Darba rezultātā tika izveidota lietotne, kas atbalsta augstāk minētās funkcijas un vairākas sekundārās funkcijas, kā arī dokumentācija, kurā aprakstītas programma…
Būla funkciju simetrijas
2015
Šajā bakalaura darbā pētītas Būla funkciju simetrijas, koncentrējoties tieši uz NPN-simetrijām un ekvivalencēm, kurām ir daudz praktisku un teorētisku pielietojumu. Tika uzstādīts mērķis izpētīt NPN-simetriju skaitus n bitu Būla funkcijām, kā arī pierādīt vai apgāzt hipotēzi, ka katrai n bitu Būla funkcijai ir vismaz viena NPN-simetrija. Mērķu sasniegšanai tika veikta zinātniskās literatūras izpēte, lai noskaidrotu, kas šajā jautājumā jau ir izdarīts. Tā kā nevienā no aplūkotajiem rakstiem tieši šāds uzdevums nebija risināts, tika izveidotas datorprogrammas, ar kuru palīdzību tika ievākta nepieciešamā statistika par Būla funkciju NPN-simetrijām. Tika noskaidrots arī, ka izvirzītā hipotēze i…
Atbalsta bibliotēka Būla funkciju izpētei
2015
Būla funkcijas ir joprojām aktuāls pētījumu objekts. Tās izmanto sarežģītības teorijā, elektrisko slēgumu projektēšanā, kvantu kriptogrāfijā un citur. Šī darba mērķis ir izveidot pro-grammatūru vienkāršāko Būla funkciju raksturotāju noteikšanai: jūtīguma, bloku jūtīguma, pārstāvošo un tuvināto polinomu aprēķināšanai. Tās galvenais pielietojums varētu būt pielie-tošana projektā “Kvantu algoritmi” (angliski: QALGO: Quantum Algorithmics), kas pēta arī Būla funkcijas. Motivācija šādas programmas izstrādei nāk no pētnieku puses, kas ikdienā no-darbojas ar funkciju un algoritmu sarežģītības pētīšanu, kā procesā ir nepieciešams veikt atse-višķu raksturotāju noteikšanu pastarpinātiem algoritmiem va…
Jaunas sakarības starp Būla funkciju jutīgumu un bloku jutīgumu
2015
Darbā tiek pētīta neatrisināta problēma skaitļošanas sarežģītības teorijā – Būla funkciju jutīguma s(f) saistība ar tādiem sarežģītības mēriem kā bloku jutīgums bs(f) un sertifikātu sarežģītība C(f). Populāra hipotēze apgalvo, ka jutīgums ir polinomiāli saistīts ar bloku jutīgumu un bs(f) = O(s(f)^c) kādai konstantei c. Līdz šim labākais zināmais novērtējums no augšas abiem mēriem ir eksponenciāls, bs(f) ≤ C(f) ≤ 2^(s(f)-1) s(f) - s(f) + 1, bet labākie atrastie piemēri sasniedz tikai kvadrātisku atstarpi, bs(f) = Ω(s(f)^2). Šajā darbā tiek pierādīts jauns novērtējums no augšas, bs(f) ≤ C(f) ≤ max(2^(s(f)-1) (s(f) - 1/3), s(f)).
Kvantu algoritmu konstruēšana, izmantojot čaulu programmas
2017
Čaulu programma ir lineāri algebrisks skaitļošanas modelis, ar kura palīdzību var konstruēt programmas Būla funkciju rēķināšanai. Ir zināms, kā čaulu programmu var pārtaisīt par kvantu vaicājošo algoritmu. Pie tam, čaulu programmām var definēt sarežģītību tā, ka pārtaisītajam kvantu algoritmam sarežģītība sakristu ar čaulu programmas sarežģītību. Līdz ar to čaulu programmas ir spēcīgs rīks kvantu algoritmu konstruēšanai. Ir zināms veids, kā uztaisīt čaulu programmu, kura rēķinātu Būla formulu F(x_1,...,x_n), kas sastāv no loģiskajiem elementiem (NOT, OR, AND). Šī darba mērķis ir izveidot metodi, ar kuras palīdzību varētu konstruēt pēc iespējas optimālas čaulu programmas, kuras rēķinātu Būla…
Rēķināšanas sarežģītības samazināšana ar nejaušību lietošanu
2016
Maģistra darbs „Rēķināšanas sarežģītības samazināšana ar nejaušības lietošanu” iekļauj pētījumu par varbūtisko pieeju rēķināšanas sarežģītības samazināšanai un apskata divus uzdevumus, proti, mulitilneāru polinomu ģenerēšanu un dārza šļūteņu modeļa izveidi, kuriem autore ir veikusi esošo risinājumu izpēti un izstrādājusi savus risinājumu algoritmus. Multilineāru polinomu ģenerēšanas problēmai, kurā tiek ģenerēti polinomi, kura atbilstu Būla funkcijai, ir veikta multilineāro polinomu izpēte, lai noteiktu to īpašības, kuras tiek izmantotas autores izstrādātajā polinomu ģenerēšanas varbūtiskajā algoritmā. Dārza šļūteņu (Garden - Hose) modeļa problēmai, kura ir salīdzinoši jauna (2013. gadā def…
Eksakto kvantu vaicājošo algoritmu sarežģītība nejaušām Būla funkcijām
2018
Ir pierādīts, ka nejaušai n-bitu Būla funkcijai optimālam kvantu vaicājošajam algoritmam ir nepieciešami aptuveni n/2 vaicājumi, ja algoritmam ir atļauts kļūdīties ar nelielu varbūtību, taču eksaktajiem algoritmiem šī sarežģītība nav zināma. Šajā darbā tiek pētītas polinomiālās metodes iespējas eksaktas kvantu vaicājumu sarežģītības apakšējas robežas pierādīšanai. Tiek apskatīti tādi polinomi, kuru kvadrātu summa pārstāv doto Būla funkciju. Pirmkārt, ar pusnoteiktās programmēšanas palīdzību tiek skaitliski parādīts priekš n<=8, ka nejaušai n-bitu Būla funkcijai pietiekami precīzi |(n+1)/2| pakāpes polinomi eksistē ar lielu varbūtību. Otrkārt, tiek pierādīts, ka gandrīz visas Būla funkcijas …
Ultrametriski algoritmi
2015
Maģistra darbā tiek pētīta ultrametriska galīga automāta un ultrametriska vaicājošā algoritma definīcija, kas paredz p-adisku skaitļu izmantošanu amplitūdu norādīšanā. Lasītājs tiek iepazīstināts ar p-adisku skaitļošanas sistēmu un absolūtās vērtības jēdzienu. Darba ietvaros tiek izstrādātas ultrametrisku automātu realizācijas dažādu valodu atpazīšanai. Ultrametrisku automātu rēķināšanas sarežģītība tiek novērtēta pēc stāvokļu skaita automātā. Tiek apskatīts ultrametrisks vaicājošais algoritms, kas pārbauda Heminga koda pareizību. Darbā tiek pētītas ultrametrisku algoritmu priekšrocības salīdzinot ar klasiskām un kvantu skaitļošanas teorijas pamatkoncepcijām.